package main

import (
	. "local/algorithm/util"
)

func equalPartition(root *TreeNode) bool {
	var dfs func(root *TreeNode) int
	var stack []int
	dfs = func(root *TreeNode) int {
		if root == nil {
			return 0
		}

		if root.Left == nil && root.Right == nil {
			return root.Val
		}

		left := dfs(root.Left)
		right := dfs(root.Right)
		stack = append(stack, root.Val+left+right)
		return root.Val + left + right
	}
	sum := dfs(root)
	stack = stack[:len(stack)-1]
	if sum%2 == 0 {
		for i := 0; i < len(stack); i++ {
			if stack[i] == sum/2 {
				return true
			}
		}
	}
	return false
}
